package _back_tracking

import org.junit.Assert
import org.junit.Test

/*
https://leetcode.cn/problems/subsets/description/
https://programmercarl.com/0078.%E5%AD%90%E9%9B%86.html

78. 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：
输入：nums = [0]
输出：[[],[0]]
 */
class leetcode_78 {
    @Test
    fun test_1() {
        val actual = subsets(intArrayOf(1, 2, 3))
        val expect: ArrayList<ArrayList<Int>> = arrayListOf(
            arrayListOf(), arrayListOf(1), arrayListOf(1, 2), arrayListOf(1, 2, 3), arrayListOf(1, 3), arrayListOf(2), arrayListOf(2, 3), arrayListOf(3)
        )
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val actual = subsets(intArrayOf(0))
        val expect: ArrayList<ArrayList<Int>> = arrayListOf(
            arrayListOf(), arrayListOf(0)
        )
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    fun subsets(nums: IntArray): List<List<Int>> {
        /*
        回溯法
        子集问题：不需要去重，收集所有节点
        求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树。
         */
        val result: ArrayList<ArrayList<Int>> = ArrayList()
        val path: ArrayList<Int> = ArrayList()
        backtracking(nums, 0, path, result)
        return result
    }

    private fun backtracking(nums: IntArray, startIndex: Int, path: ArrayList<Int>, result: ArrayList<ArrayList<Int>>) {
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        // 终止条件
        if (nums.isEmpty()) {
            return
        }
        if (startIndex > nums.size) { // 可以不需要加终止条件，因为startIndex >= nums.size()，本层for循环本来也结束了
            return
        }
        // 收集结果
        val items: ArrayList<Int> = ArrayList<Int>()
        items.addAll(path)
        result.add(items)

        // 3 确定单层递归的处理逻辑
        for (i in startIndex..nums.size - 1) {
            // 处理节点
            path.add(nums[i])

            // 递归
            backtracking(nums, i + 1, path, result)

            // 回溯
            path.removeAt(path.size - 1)
        }
    }
}